@c Cells, queues, hash tables, & weak references subsections.

@node Cells
@subsection Cells

@stindex cells
Scheme48 also provides a simple mutable cell data type from the
@code{cells} structure.  It uses them internally for local, lexical
variables that are assigned, but cells are available still to the rest
of the system for general use.

@deffn procedure make-cell contents @returns{} cell
@deffnx procedure cell? object @returns{} boolean
@deffnx procedure cell-ref cell @returns{} value
@deffnx procedure cell-set! cell value @returns{} unspecified
@code{Make-cell} creates a new cell with the given contents.
@code{Cell?} is the disjoint type predicate for cells.  @code{Cell-ref}
returns the current contents of @var{cell}.  @code{Cell-set!} assigns
the contents of @var{cell} to @var{value}.
@end deffn

Examples:

@lisp
(define cell (make-cell 42))
(cell-ref cell)                         @result{} 42
(cell? cell)                            @result{} #t
(cell-set! cell 'frobozz)
(cell-ref cell)                         @result{} frobozz@end lisp

@node Queues
@subsection Queues

@cindex FIFOs
@stindex queues
The @code{queues} structure exports names for procedures that operate
on simple first-in, first-out queues.

@deffn procedure make-queue @returns{} queue
@deffnx procedure queue? object @returns{} boolean
@code{Make-queue} constructs an empty queue.  @code{Queue?} is the
disjoint type predicate for queues.
@end deffn

@deffn procedure queue-empty? queue @returns{} boolean
@deffnx procedure empty-queue! queue @returns{} unspecified
@code{Queue-empty?} returns @code{#t} if @var{queue} contains zero
elements or @code{#f} if it contains some.  @code{Empty-queue!} removes
all elements from @var{queue}.
@end deffn

@deffn procedure enqueue! queue object @returns{} unspecified
@deffnx procedure dequeue! queue @returns{} value
@deffnx procedure maybe-dequeue! queue @returns{} value or @code{#f}
@deffnx procedure queue-head queue @returns{} value
@code{Enqueue!} adds @var{object} to @var{queue}.  @code{Dequeue!}
removes & returns the next object available from @var{queue}; if
@var{queue} is empty, @code{dequeue!} signals an error.
@code{Maybe-dequeue!} is like @code{dequeue!}, but it returns @code{#f}
in the case of an absence of any element, rather than signalling an
error.  @code{Queue-head} returns the next element available from
@var{queue} without removing it, or it signals an error if @var{queue}
is empty.
@end deffn

@deffn procedure queue-length queue @returns{} integer
Returns the number of objects in @var{queue}.
@end deffn

@deffn procedure on-queue? queue object @returns{} boolean
@deffnx procedure delete-from-queue! queue object @returns{} unspecified
@code{On-queue?} returns true if @var{queue} contains @var{object} or
@code{#f} if not.  @code{Delete-from-queue!} removes the first
occurrence of @var{object} from @var{queue} that would be dequeued.
@end deffn

@deffn procedure queue->list queue @returns{} list
@deffnx procedure list->queue list @returns{} queue
These convert queues to and from lists of their elements.
@code{Queue->list} returns a list in the order in which its elements
were added to the queue.  @code{List->queue} returns a queue that will
produce elements starting at the head of the list.
@end deffn

Examples:

@lisp
(define q (make-queue))
(enqueue! q 'foo)
(enqueue! q 'bar)
(queue->list q)                         @result{} (foo bar)
(on-queue? q 'bar)                      @result{} #t
(dequeue! q)                            @result{} 'foo
(queue-empty? q)                        @result{} #f
(delete-from-queue! queue 'bar)
(queue-empty? q)                        @result{} #t
(enqueue! q 'frobozz)
(empty-queue! q)
(queue-empty? q)                        @result{} #t
(dequeue! q)                            @error{} empty queue@end lisp

Queues are integrated with Scheme48's @embedref{Optimistic concurrency,
optimistic concurrency} facilities, in that every procedure exported
except for @code{queue->list} ensures fusible atomicity in operation
--- that is, every operation except for @code{queue->list} ensures that
the transaction it performs is atomic, and that it may be fused within
larger atomic transactions, as transactions wrapped within
@code{call-ensuring-atomicity} @etc{} may be.

@node Hash tables
@subsection Hash tables

@stindex tables
Scheme48 provides a simple hash table facility in the structure
@code{tables}.

@deffn procedure make-table [hasher] @returns{} table
@deffnx procedure make-string-table @returns{} string-table
@deffnx procedure make-symbol-table @returns{} symbol-table
@deffnx procedure make-integer-table @returns{} integer-table
Hash table constructors.  @code{Make-table} creates a table that hashes
keys either with @var{hasher}, if it is passed to @code{make-table}, or
@code{default-hash-function}, and it compares keys for equality with
@code{eq?}, unless they are numbers, in which case it compares with
@code{eqv?}.  @code{Make-string-table} makes a table whose hash function
is @code{string-hash} and that compares the equality of keys with
@code{string=?}.  @code{Make-symbol-table} constructs a table that
hashes symbol keys by converting them to strings and hashing them with
@code{string-hash}; it compares keys' equality by @code{eq?}.  Tables
made by @code{make-integer-table} hash keys by taking their absolute
value, and test for key equality with the @code{=} procedure.
@end deffn

@deffn procedure make-table-maker comparator hasher @returns{} table-maker
Customized table constructor constructor: this returns a nullary
procedure that creates a new table that uses @var{comparator} to compare
keys for equality and @var{hasher} to hash keys.
@end deffn

@deffn procedure table? object @returns{} boolean
Hash table disjoint type predicate.
@end deffn

@deffn procedure table-ref table key @returns{} value or @code{#f}
@deffnx procedure table-set! table key value @returns{} unspecified
@code{Table-ref} returns the value associated with @var{key} in
@var{table}, or @code{#f} if there is no such association.
If @var{value} is @code{#f}, @code{table-set!} ensures that there is no
longer an association with @var{key} in @var{table}; if @var{value} is
any other value, @code{table-set!} creates a new association or assigns
an existing one in @var{table} whose key is @var{key} and whose
associated value is @var{value}.
@end deffn

@deffn procedure table-walk proc table @returns{} unspecified
@code{Table-walk} applies @var{proc} to the key & value, in that order
of arguments, of every association in @var{table}.
@end deffn

@deffn procedure make-table-immutable! table @returns{} table
This makes the structure of @var{table} immutable, though not its
contents.  @code{Table-set!} may not be used with tables that have been
made immutable.
@end deffn

@deffn procedure default-hash-function value @returns{} integer-hash-code
@deffnx procedure string-hash string @returns{} integer-hash-code
Two built-in hashing functions.  @code{Default-hash-function} can hash
any Scheme value that could usefully be used in a @code{case} clause.
@code{String-hash} is likely to be fast, as it is implemented as a VM
primitive.  @code{String-hash} is the same as what the @code{features}
structure exports under the same name.
@end deffn

@node Weak references
@subsection Weak references

@stindex weak
Scheme48 provides an interface to weakly held references in basic weak
pointers and @dfn{populations}, or sets whose elements are weakly held.
The facility is in the structure @code{weak}.

@subsubsection Weak pointers

@deffn procedure make-weak-pointer contents @returns{} weak-pointer
@deffnx procedure weak-pointer? object @returns{} boolean
@deffnx procedure weak-pointer-ref weak-pointer @returns{} value or @code{#f}
@code{Make-weak-pointer} creates a weak pointer that points to
@var{contents}.  @code{Weak-pointer?} is the weak pointer disjoint type
predicate.  @code{Weak-pointer-ref} accesses the value contained within
@code{weak-pointer}, or returns @code{#f} if there were no strong
references to the contents and a garbage collection occurred.  Weak
pointers resemble @embedref{Cells, cells}, except that they are
immutable and hold their contents weakly, not strongly.
@end deffn

@subsubsection Populations (weak sets)

@deffn procedure make-population @returns{} population
@deffnx procedure add-to-population! object population @returns{} unspecified
@deffnx procedure population->list population @returns{} list
@deffnx procedure walk-population proc population @returns{} unspecified
@code{Make-population} constructs an empty population.
@code{Add-to-population!} adds @var{object} to the population
@var{population}.  @code{Population->list} returns a list of the
elements of @var{population}.  Note, though, that this can be
dangerous in that it can create strong references to the population's
contents and potentially leak space because of this.
@code{Walk-population} applies @var{proc} to every element in
@var{population}.
@end deffn
